
%%%%%%%%%%%%%%%%%%%%%%% file typeinst.tex %%%%%%%%%%%%%%%%%%%%%%%%%
%
% This is the LaTeX source for the instructions to authors using
% the LaTeX document class 'llncs.cls' for contributions to
% the Lecture Notes in Computer Sciences series.
% http://www.springer.com/lncs       Springer Heidelberg 2006/05/04
%
% It may be used as a template for your own input - copy it
% to a new file with a new name and use it as the basis
% for your article.
%
% NB: the document class 'llncs' has its own and detailed documentation, see
% ftp://ftp.springer.de/data/pubftp/pub/tex/latex/llncs/latex2e/llncsdoc.pdf
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\documentclass[runningheads,a4paper]{llncs}

\usepackage{amsmath,amsfonts,amssymb,graphics,epsf}
\setcounter{tocdepth}{3}
\usepackage{graphicx}

\usepackage{algorithmic}
\usepackage{algorithm}

\usepackage{url}

\newtheorem{observation}{Observation}

%% You may enlarge this list if necessary

\urldef{\mailsa}\path|{alfred.hofmann, ursula.barth, ingrid.haas, frank.holzwarth,|
\urldef{\mailsb}\path|anna.kramer, leonie.kunz, christine.reiss, nicole.sator,|
\urldef{\mailsc}\path|erika.siebert-cole, peter.strasser, lncs}@springer.com|    
\newcommand{\keywords}[1]{\par\addvspace\baselineskip
\noindent\keywordname\enspace\ignorespaces#1}



%%
%% Here you may place your macros using \newcommand{}{}
%%
\def\hull#1{{\text{CH}(#1)}}
\def\ch#1{{\hull{#1}}}

\begin{document}

\mainmatter  % start of an individual contribution

% first the title is needed
\title{Dynamic circle separability of convex polygons}

% a short form should be given in case it is too long for the running head
\titlerunning{Dynamic circle separability of convex polygons}

% the name(s) of the author(s) follow(s) next
%
% NB: Chinese authors should write their first names(s) in front of
% their surnames. This ensures that the names appear correctly in
% the running heads and the author index.
%
\author{Luis Barba$^1$\and Jorge Urrutia$^2$}
%
\authorrunning{Lecture Notes in Computer Science}
% (feature abused for this document to repeat the title also on left hand pages)

% the affiliations are given next; don't give your e-mail address
% unless you accept that it will be published
\institute{${}^1$ %%
Posgrado en Ciencia e Ingenier\'ia de la Computaci\'on,
Universidad Nacional Aut\'onoma de M\'exico\\
${}^2$ %%
Instituto de Matem\'aticas,
Universidad Nacional Aut\'onoma de M\'exico}
%\paperemail{l.barba@uxmcc2.iimas.unam.mx}

%\paperemail{urrutia@matem.unam.mx}
%
% NB: a more complex sample for affiliations and the mapping to the
% corresponding authors can be found in the file "llncs.dem"
% (search for the string "\mainmatter" where a contribution starts).
% "llncs.dem" accompanies the document class "llncs.cls".
%

\toctitle{Lecture Notes in Computer Science}
\tocauthor{Authors' Instructions}
\maketitle


\begin{abstract}
Let $P$ be a convex polygon with $n$ vertices.
In this paper we study a new variant of the circular separability problem in which
we are allowed to preprocess the polygon $P$ into a data structure supporting queries of the following form:
Given a convex polygon $Q$ as a list of its $m$ vertices, 
report the minimum circle containing $P$ and whose interior does not intersects $Q$.
Our data structure can be constructed in linear time using $O(n)$ space, 
and answers queries in $O(\log n \log m)$ time.
\keywords{Circular separability, furthest point Voronoi diagram}
\end{abstract}


\section{Introduction}
Let $\Phi$ be a family curves on $\mathbb{R}^2$ such that for every $\phi\in \Phi$, $\mathbb{R}^2 - \phi$ has exactly two connected components $\phi_1,\phi_2$.
Let $P,Q$ be two subsets of $\mathbb{R}^2$. 
We say that $P,Q$ are $\Phi$ separable, if there exists $\phi\in \Phi$, 
such that $int(P), int(Q)$ are completely contained on $\phi_1,\phi_2$ respectively.

The separability problem recently attracted research interest, 
with $\Phi$ most often considered as the family of lines, 
circles or simple polygons on the plane.
If $P,Q$ are finite point sets on the plane, then the line separability problem can be solved using linear programing~\cite{LinearProgrammingInLinearTime}.

The problem of finding the separating polygon with minimum number of vertices between finite point sets was studied in~\cite{MinimumPolygonalSeparation}.
Aggarwal, Booth, O'Rourke and Suri studied the problem of finding the minimum separating polygon between the boundary of two nested convex polygons~\cite{Aggarwal:1985}.
Das and Joseph extended the problem to higher dimensions and 
proved that the problem of computing a separating polyhedron, 
having the minimum number of faces, 
for two nested convex polyhedra is NP-complete~\cite{DasJoseph:1990}.


The study of circular separability was developed because of the several applications it has in pattern recognition and image processing~\cite{DigitalDiskAndCompacness}~\cite{SeparatingPointsByCricles}.
In higher dimensions, Lay~\cite{SeparationBySphericalSurfaces} introduced the idea of transforming an instance of the spherical separability problem in $\mathbb{R}^d$, 
to a linear separability problem in $\mathbb{R}^{d+1}$, 
using the stereographic projection.

Anderson and Kim~\cite{DigitalDiskAndCompacness} presented 
a quadratic algorithm for solving the circular separability 
problem between any two finite planar sets. 
Bhattacharya~\cite{ComputingCircularSeparabilityOfPlanarPointSets} 
improved the running time to $O(n\log n)$, 
by computing the entire region on which the separating circles may be centered. 
Finally  Kosaraju, Megiddo and O'Rourke~\cite{ComputingCircularSeparability} found a linear time algorithm to solve the circular separability problem and proved that their algorithm is optimal.
They also proposed an $O(n\log n)$ algorithm for finding the largest separating circle of two finite point sets.
Their approach was to use the paraboloid transformation, to get an instance of a convex, quadratic minimization problem in three dimensions.

\subsection*{Results}
Let $P$ be a convex polygon with $n$ vertices.
In this paper we consider the online version of the circular separability problem in which
we are allowed to preprocess the polygon $P$ into a data structure supporting queries of the following form:
Given a convex polygon $Q$ as a list of its $m$ vertices, 
report efficiently the minimum circle containing $P$ and whose interior does not intersects $Q$.
The data structure used in this paper can be constructed in $O(n)$ time, uses $O(n)$ space, 
and allow us to answers queries in $O(\log n \log m)$ time.
Recall that linear time is required to answer the query if no preprocessing is allowed~\cite{ComputingCircularSeparability}.


\section{Preliminaries}%%%%%%%%%%

Let $P,Q$ be two convex polygons in the plane with $n, m$ vertices respectively.
Suppose for ease of description that the vertices of $P$ and $Q$ are in general position, 
and that $P$ has no four co-circular vertices. 
For ease of notation we say that every circle containing $P$ is a $P$-circle.
We also say that a circle $C$ separates $P$ from $Q$, or simply that $C$ is a separating circle, 
if $C$ is a $P$-circle and its interior does not intersects $Q$. 
In section~\ref{section:Resultados} we prove that the minimum separating circle is unique, 
therefore let $C'$ denote the minimum separating circle and let $c'$ be its center.

Note that $C'$ always contain at least two vertices of $P$, 
since otherwise an smaller separating circle could always be found; see Figure~\ref{fig:Centro en V(P)}.
Therefore $c'$ must lie on an edge of the furthest-point Voronoi diagram of the vertices of $P$.
Recall that this diagram can be seen as a tree if we handle the $n$ unbounded edges carefully;
throughout this paper we denote this tree by $\mathcal{V}(P)$. 
Also, for each vertex $p$ of $P$, let $R(p)$ be 
the farthest-point Voronoi region associated to $p$.
Let $C_{P}$ be the minimum enclosing circle of $P$, let $c_{P}$ be its center and
recall that $c_P$ lies on an edge of $\mathcal{V}(P)$, 
thus we think of $\mathcal{V}(P)$ as a rooted tree on $c_P$.
Note that given any point $x$ on an edge of the tree,
there is a unique path contained in $\mathcal{V}(P)$ joining $c_P$ with $x$, 
throughout this paper we denote this path by $T_x$.

Also, given any point $y$ in the plane, 
let $C(y)$ be the minimum $P$-circle with center on $y$
and let $\rho(y)$ be the radius of $C(y)$.
Note that if $y$ belongs to $R(p)$ for some vertex $p$ of $P$, 
then the radius of $C(y)$ is given by the distance between $y$ and $p$.

%%%%%%%%%%%%%%%%%%%%%%%%%Ejemplos
\begin{figure}[h]
\begin{center}
\includegraphics[angle=0, width=.8\textwidth]{img/centroEnV(P).pdf}
\caption{\small Every separating circle containing only one vertex of $P$ on its boundary
contains another separating circle with smaller radius containing at least two vertices.} 
\label{fig:Centro en V(P)}
\end{center}
\end{figure}


\section{The minimum separating circle}\label{section:Resultados}
In this section we start by showing some properties of the minimum separating circle, 
followed by a detailed analyze of the relationship existing between $c'$ 
and the furthest-point Voronoi diagram of the vertices of $P$.

Note that if the interiors of $Q$ and $P$ are not disjoint, 
then there is no separating circle, 
hence we will suppose that $d(P,Q)\geq0$.
It is also worth noting that if $Q$ and $C_{P}$ have disjoint interiors, 
then $C_{P}$ is trivially the minimum separating circle.
However, in any other case the solution is not trivial and will result in a $P$-circle that is tangent to the polygon $Q$.

The following observation is straightforward 
and shows the relation existing between separating circles and $P$-circles.

\begin{observation}\label{Relation P-circle separating circle}
Every $P$-circle contained on a separating circle is also a separating circle.
\end{observation}

%%%%%%%%%%%%%%%%%%%%%%%%%Ejemplos
\begin{figure}[h]
\begin{center}
\includegraphics[angle=0, width=.8\textwidth]{img/CirculosEnSegmento.pdf}
\caption{\small For every point $z\in [x,y]$ the circle $C(z)$ lies in the union of $C(x)$ and $C(y)$.} 
\label{fig:CirculosEnSegmento}
\end{center}
\end{figure}

We claim that if $x$ is a point in the tree $\mathcal{V}(P)$ 
such that $C(x)$ is a separating circle, 
then $c'$ is a point lying on an edge of $T_x$.
In order to prove the previous claim, 
we present a series of results starting with the following property of the farthest-point Voronoi diagram.

\begin{proposition}\label{Monotonia de Rho}
Let $x$ be a point lying on an edge of $\mathcal{V}(P)$. The function $\rho$ is monotonically 
increasing along the path $T_{x}$
starting at $c_P$.
\end{proposition}
\begin{proof}
Let $e$ be an edge of $T_x$ contained in the bisector of the vertices $p,p'$ of $P$, 
and consider a point $y$ moving along the edge $e$. 
Note that as we move $y$, if $d=d(y,p)=d(y,p')$ increases monotonically, 
then the radius of $C(y)$ also increases since $y$ lies on $R(p)\cap R(p')$.
Thus, moving $y$ from $c_P$ towards $x$ on $T_x$, 
we obtain that $\rho(y)$ increases monotonically on every edge along the way.
\end{proof}


\begin{observation}\label{CirculosEnSegmento}
Let $x$ and $y$ be two points on $\mathbb{R}^2$. If $z$ is a point contained in $[x,y]$, 
then $C(z)\subseteq C(x)\cup C(y)$.
\end{observation}

The previous observation implies that the minimum separating circle is unique, its proof is straightforward and  can be observed in figure~\ref{fig:CirculosEnSegmento}, also note that if $z\in [x,y]$, then $\rho(z)\leq \max\{\rho(x), \rho(y)\}$.
Furthermore this implies that if $C(x)$ and $C(y)$ are both separating circles, then for every $z\in[x,y]$, $C(z)$ is also a separating circle.

%%%%%%%%%%%%%%%%%%%%%%%%%Ejemplos
\begin{figure}[h]
\begin{center}
\includegraphics[angle=0, width=.76\textwidth]{img/AncestroComun.pdf}
\caption{\small The proof of Lemma~\ref{AncestroSeparadorGral}.} 
\label{fig:AncestroComun}
\end{center}
\end{figure}

\begin{lemma}\label{AncestroSeparadorGral}
Let $x$ and $y$ be two points on $\mathcal{V}(P)$ such that $C(x)$ and $C(y)$ are separating circles.
If $z$ is the lowest common ancestor of $x$ and $y$ in the rooted tree $\mathcal{V}(P)$, then $C(z)$ is a separating circle; moreover $\rho(z) \leq \min\{\rho(x), \rho(y)\}$.
\end{lemma}
\begin{proof}
Suppose that $y\notin T_x$ and $x\notin T_y$, otherwise the result follows trivially.
Let $e_x, e_y$ be the first edges on the paths joining $z$ with $x$ and $z$ with $y$ respectively.
Recall that we assumed that no four vertices of $P$ are co-circular, hence the degree of $z$ on the tree is exactly three, 
therefore  $e_x$ and $e_y$ are consecutive edges in the radial order from $z$, 
thus $e_x,e_y$ and $z$ belong to the boundary of the same Voronoi region $R(p)$, with $p$ being a vertex of $P$.

Let $\ell_{z,p}$ be the straight line through $z$ and $p$. 
Note that $\ell_{z,p}$ enters $R(p)$ at the point $z$ and from there it is completely contained in $R(p)$, 
thus $\ell_{z,p}$ leaves $x$ and $y$ in different semiplanes.
Furthermore, if we let $z'$ be the intersection point between $[x,y]$ and $\ell_{z,p}$, 
then $z'$ also belongs to $R(p)$.
Recall that Observation~\ref{CirculosEnSegmento} implies that $C(z')$ is a separating circle,
additionally observe that $z', z, p$ are co-linear and that $d(z',p),d(z,p)$ define the radius of $C(z'),C(z)$ respectively, 
therefore $C(z)\subseteq C(z')$; see Figure~\ref{fig:AncestroComun}.
Since $C(z)$ is a $P$-circle contained inside a separating circle,
Observation~\ref{Relation P-circle separating circle} implies that $C(z)$ is also a separating circle. 
Moreover, since $z$ is a common ancestor of $x$ and $y$, we infer from Proposition~\ref{Monotonia de Rho} that $\rho(z)< \min\{\rho(x), \rho(y)\}$.
\end{proof}



\begin{theorem}\label{c' en T_s}
Let $s$ be a point on an edge of $\mathcal{V}(P)$. If $C(s)$ is a separating circle, 
then $c'$  belong to $T_s$.
\end{theorem}
\begin{proof}
Proceed by contradiction and assume that $c'$ does not belong to $T_s$.
Let $z$ be the lowest common ancestor of $c'$ and $s$,
note that Lemma~\ref{AncestroSeparadorGral} implies that $C(z)$ is a separating circle 
and since $z$ is an ancestor of $c'$, Proposition~\ref{Monotonia de Rho} implies that $\rho(z)< \rho(c')$ which is a contradiction; 
our result follows.
\end{proof}

Note that the previous theorem, in conjunction with Observation~\ref{Monotonia de Rho}, 
imply that for every point $x$ between $c'$ and $c_P$ on $T_s$, since $\rho(x) < \rho(c')$,
$C(x)$ is a circle that intersects the interior of $Q$.
Now, If we think of moving a point $y$ continuously from $s$ towards $c_P$ on $T_s$, 
then $C(y)$ will be shrinking along the path and getting closer to $Q$, 
until intersecting it for the first time when $y$ reaches $c'$, 
thus the next result follows.

\begin{corollary}\label{TangentToQ}
The minimum separating circle is either $C_P$ or is a circle that is tangent to the polygon $Q$.
\end{corollary}


\section{The algorithm}%%%
Recall that our objective is to design a data structure on $P$ to answer the following query efficiently:
Given any convex polygon $Q$, compute the minimum separating circle.
In the previous section we presented the relation existing between the minimum separating circle and the tree $\mathcal{V}(P)$,
in this section we use that relation to present a data structure on $\mathcal{V}(P)$ that allow us to perform a binary search on the paths contained in $\mathcal{V}(P)$.

\subsection{Preprocessing}%%%%%
Given a convex polygon $P$ with $n$ vertices, 
we compute the farthest-point Voronoi diagram of the vertices of $P$ in 
$O(n)$ time~\cite{LinearVoronoiDiagramForConvexPolygon}.
Assume that the diagram is stored as a tree $\mathcal{V}(P)$ with $n$ unbounded edges, 
such that every edge and every vertex of the tree has a set of pointers to the vertices of $P$ defining it.
We also assume that every Voronoi region is stored as a convex polygon and
that every vertex $p$ of $P$ has a pointer to $R(p)$.

Additionally we compute the minimum $P$-circle $C_P$ along with its center $c_P$ in linear time~\cite{LinearTimeAlgorithmsForLinearProgramming}.
At this point we can check if $C_P$ is or not a separating circle by computing the distance between $c_P$ and $Q$ in $O(\log m)$ time~\cite{ComputingExtremeDistancesBetweenConvexPolygons}, 
if it is greater than the radius of $C_P$, then $C_P$ is the minimum separating circle.
Thus we will assume from now on that $C_P$ is not the minimum separating circle, 
which implies that $C_P$ intersects $Q$ and that $C'$ is a circle tangent to the polygon $Q$.

Once $c_P$ has been computed, if $c_P$ is not a vertex of $\mathcal{V}(P)$, 
then we insert it on the tree by splitting the edge where it belongs,
then we perform a DFS to root the tree on $c_P$ in linear time. 
We assume that for every vertex $v$ in $\mathcal{V}(P)$, $parent(v)$ represents the parent of $v$ on the rooted tree.

%%%%%%%%%%%%%%%%%%%%%%%%%Ejemplos
\begin{figure}[h]
\begin{center}
\includegraphics[angle=0, width=1\textwidth]{img/DataStructure.pdf}
\caption{\small The data structure on $\mathcal{V}(P)$ as seen on a path with 32 vertices.} 
\label{fig:DataStructure}
\end{center}
\end{figure}

Let $x$ be a point lying on an edge of $\mathcal{V}(P)$ and consider the path $T_x$,
we want our data structure to support binary searches on $T_x$, thus
to guide the binary search we will use an oracle that answers queries of the following form:
Given a vertex $v$ of $T_x$,
decide if the searched point lies either between $c_P$ and $v$ or between $v$ and $x$ on the path $T_x$.
Note that on each query to the oracle we are able to discard all the vertices lying on one side of the vertex $v$.

We will use the data structure on $\mathcal{V}(P)$ proposed by Das, Karmakar, Nandy and Roy
in~\cite{ConstrainedMinimumEnclosingCircleWithCenterOnAQueryLineSegment}, this structure can be constructed in $O(n)$ time and uses linear space by storing two extra pointers $ptr_1,ptr_2$ on each vertex of the tree; see Figure~\ref{fig:DataStructure}.
Intuitively these extra pointers allow us to perform a search for a point on the path $T_x$ by
asking the oracle a logarithmic number of queries with respect to the length of $T_x$.
In the next section we give a full explanation of the algorithm, 
nevertheless details about the construction and performance of the data structure can be found in~\cite{ConstrainedMinimumEnclosingCircleWithCenterOnAQueryLineSegment}.


\subsection{The search for $c'$ on the tree}
We present now an algorithm to determine the position of $c'$ on the tree $\mathcal{V}(P)$ given any query convex polygon $Q$.
We first find a point $s$ on an edge of $\mathcal{V}(P)$ such that $C(s)$ is a separating circle,
then we search for $c'$ on $T_s$ using our data structure, 
the algorithm is described as follows.

%%%%%%%%%%%%%%%%%%%%%%%%%Ejemplos
\begin{figure}[h]
\begin{center}
\includegraphics[angle=0, width=.7\textwidth]{img/ConstruccionS_0.pdf}
\caption{\small Construction of $s$.} 
\label{fig:PrimerCirculoSeparador}
\end{center}
\end{figure}

We start by constructing a 
straight line $L$ separating $P$ and $Q$ in $O(\log n + \log m)$ time~\cite{ComputingExtremeDistancesBetweenConvexPolygons}.
Let us assume that $p_{_L}$ is the unique point in $P$ closest to $L$,
otherwise rotate $L$ slightly
keeping $P$ and $Q$ separated by $L$. 
Let $L_{\perp}$ be the perpendicular to $L$ that contains $p_{_L}$ and let $s$ be the intersection of $L_{\perp}$ with the boundary of $R(p_{_L})$.
This intersection exists since $L$ can be thought as a $P$-circle with center at infinity lying on the line $L_\perp$.
Thus if we let $z$ be a point on $L_\perp$ sufficiently far away such that $C(z)$ looks like $L$ in the vicinity of $P$ and $Q$, 
then $C(z)$ will be a separating circle and the farthest vertex of $P$ from $z$ will be $p_{_L}$.
This implies that $z$ will belong to $R(p_{_L})$ and therefore $s$ is well defined.

Note that $d(s,p_{_L})$ defines the radius of $C(s)$, hence $C(s)$ is contained on the same semi-plane defined by $L$ containing $P$, this implies that $C(s)$ is a separating circle and that $s$ lies on an edge of $\mathcal{V}(P)$; see Figure~\ref{fig:PrimerCirculoSeparador}. 
Assume that $s$ lies on the edge $xy$ of $\mathcal{V}(P)$ with $\rho(x) > \rho(y)$ and 
let $T_{x} = ( c_P = u_0, \ldots, u_{r-1} = y,  u_r = x)$ be the path of length $r+1$ joining $c_P$ with $x$ in $\mathcal{V}(P)$, thus Theorem~\ref{c' en T_s} implies that $c'$ is a point lying on an edge of $T_x$.

Recall we are using the data structure proposed by Das, Karmakar, Nandy and Roy~\cite{ConstrainedMinimumEnclosingCircleWithCenterOnAQueryLineSegment}, 
this structure uses an oracle answering queries of the following form:
Given a vertex $v$ of $T_x$,
decide if $c'$ lies either between $c_P$ and $v$ or between $v$ and $x$ on the path $T_x$.
In our problem if $C(v)$ is a separating circle, then Theorem~\ref{c' en T_s} implies that $c'$ lies between $v$ and $c_P$, otherwise $c'$ lies between $x$ and $v$, thus we can implement the oracle with input $v$ as follows.

\begin{algorithm}
\caption{Oracle algorithm to determine if $C(v)$ is a separating circle}
\begin{algorithmic}[1]
	\STATE Calculate in constant time $\rho(v)$.
	\STATE Calculate $d(v, Q)$ in $O(\log m)$ time~\cite{ComputingExtremeDistancesBetweenConvexPolygons}.
	\IF{$\rho(v) = d(v,Q)$}
		\STATE  Finish and return $c'=v$.
	\ENDIF
	\IF{$\rho(v) > d(v,Q)$}
		\STATE $C(v)$ is not a separating circle, return \FALSE.
	\ELSE
		\STATE $C(v)$ is a separating circle, return \TRUE.
	\ENDIF
\end{algorithmic}
\end{algorithm}


Once the oracle has been implemented, we will use the algorithm proposed in ~\cite{ConstrainedMinimumEnclosingCircleWithCenterOnAQueryLineSegment} to perform a binary search on $T_{x} = ( c_P = u_0, \ldots, u_r = x)$ for $c'$. 
This algorithm works in two phases, 
during the first one we advance on the path using the pointer $ptr_1$ recursively until finding a vertex $u$ being an ancestor of $x$,
such that $C(u)$ is a separating circle but $C(u.ptr_1)$ is not.
Since $c'$ lies between $u$ and $u.ptr_1$, the second part of the algorithm uses $ptr_2$ to search on the path joining $u$ and $u.ptr_1$, 
until finding two consecutive vertices, such that the first one is a separating circle but the second one is not.

\begin{algorithm}\label{alg:FirstPhase}
\caption{First phase}
\begin{algorithmic}[1]
	\STATE Define the start vertex, $u\gets u_r$.
	\STATE Move forward using the pointer $ptr_1$, $v\gets u.ptr_1$.\label{alg:paso2}
	\STATE Perform an oracle search on $v$.
	\IF{$C(v)$ is a separating circle}
		\STATE Move forward, $u\gets v$ and return to step~\ref{alg:paso2}.
	\ELSE
		\STATE $c'$ lies between $u$ and $u.ptr_1$, finish and return $u$.
	\ENDIF
\end{algorithmic}
\end{algorithm}



\begin{algorithm}\label{alg:SecondPhase}
\caption{Second phase}
\begin{algorithmic}[1]
	\STATE Define the start vertex, $v\gets u.ptr_2$.\label{alg2:paso1}
	\STATE Perform an oracle search on $v$.\label{alg2:paso2}
	\IF{$C(v)$ is a separating circle}
		\STATE Move forward, $u\gets v$ and return to step~\ref{alg2:paso1}.
	\ELSE
		\IF{$u,v$ are consecutive vertices in $T_x$}
			\STATE Finish and return $[u,v]$.
		\ELSE
			\STATE $u\gets parent(u)$ and return to step~\ref{alg2:paso2}.
		\ENDIF
	\ENDIF
\end{algorithmic}
\end{algorithm}

When the algorithm finishes two possibilities arise. If $c'$ is a vertex on $\mathcal{V}(P)$, then we will find it and report it in $O(\log n)$ steps.
Otherwise, if $c'$ is an interior point of an edge of $\mathcal{V}(P)$, then our algorithm will return an edge $S=[u,v]$ such that $c'\in S$.
Since the number of steps of the binary search is $O(\log n)$~\cite{ConstrainedMinimumEnclosingCircleWithCenterOnAQueryLineSegment} and on each step we perform a query to the oracle requiring $O(\log m)$ time, 
the complexity of the previous search is $O(\log n \log m)$.


%%%%%%%%%%%%%%%%%%%%%%%%%Ejemplos
\begin{figure}[h]
\begin{center}
\includegraphics[angle=0, width=.8\textwidth]{img/RegionQ_S.pdf}
\caption{\small The set $Q_S$ and the point $q'$ defined as the only intersection point between $C'$ and the boundary of $Q$.} 
\label{fig:RegionQ_S}
\end{center}
\end{figure}

\subsection{Searching on the segment}
Assume that $S=[u,v]$ is the segment reported by the previous algorithm, 
thus $C(u)$ is a separating circle but $C(v)$ is not. 
Also assume that the edge $S$ of $\mathcal{V}(P)$ is defined by the vertices $p_0,p_1$ of $P$, 
therefore $S$ is contained in the bisector of $p_0$ and $p_1$.
Since the minimum separating circle is a circle tangent to $Q$,
in this section we will perform a binary search on the vertices of $Q$ to find a point $q'$ on the boundary of $Q$, such the circumcircle of the triangle $\triangle(p_0q'p_1)$ has center $c'$.


Let $y$ be a point in $\mathbb{R}^2$, we say that a point $q$ on the boundary of $Q$ is visible from $y$, if the segment $[q,y]$ intersects $Q$ only at the point $q$.
Let $Q_{S}$ be the set of points on the boundary of $Q$ visible from every point in $S$.
Since $Q$ is convex, it suffices to consider the set of points in $Q$ that are visible from $u$ and from $v$, 
thus $Q_S$ can be computed in $O(\log m)$ time; see Figure~\ref{fig:RegionQ_S}.
Recall that $C'$ denotes the minimum separating circle and let $q'$ be the only point of intersection between $C'$ and $Q$. 
Clearly $q'$ is a point in $Q_{S}$ since $c'$ belongs to $S$ and $C'$ contains no point of $Q$ in its interior.

%%%%%%%%%%%%%%%%%%%%%%%%%Ejemplos
\begin{figure}[h]
\begin{center}
\includegraphics[angle=0, width=.5\textwidth]{img/NotUnimodalInAllQ.pdf}
\caption{\small Since the circle $C(u)$ intersects $Q$ in more that two points, $\tau(x)$ is not a unimodal function when defined on the boundary of $Q$, nevertheless it is unimodal when defined on $Q_S$.} 
\label{fig:NotUnimodalInAllQ}
\end{center}
\end{figure}

Given three points $yzw\in \mathbb{R}^2$, let $C(yzw)$ be the circumcircle of the triangle $\triangle(yzw)$.
We would like a way to associate a point on $S$ to every point in $Q_S$, 
so that we can perform a search for $c'$ using the vertices lying in $Q_S$.
Note that for any point $x$ in $Q_S$, the center of $C(p_0xp_1)$ lies on the bisector of $p_0,p_1$, 
also note that the radius of $C(p_0,xp_1)$ increases as we move $x$ towards $q'$ and decreases otherwise.
Formally let $\tau(x)$ be the radius of the circle $C(p_{0}xp_{1})$,
it is easy to see that $\tau(x)$ defines an unimodal function on the points in $Q_{S}$ when traversed in clockwise order on the boundary of $Q$, and that it attains its maximum at $q'$.
This result allow us to perform a binary search for $q'$ on the vertices of $Q$ lying on $Q_S$. 
Note that we need to restrict the search to $Q_S$ since $\tau(x)$ is not unimodal if we look at all points on the boundary of $Q$; see Figure~\ref{fig:NotUnimodalInAllQ}.



\subsection{The search for $q'$}
Let $Q_{S}^{*} = \{q_0, q_1, \ldots, q_{k}\}$ be the set of vertices of $Q$ lying inside $Q_S$. 
Since $q'$ lies on an edge between two consecutive vertices of $Q_{S}^{*}$, 
we are able to perform a binary search for $q'$ on the sorted list $Q_{S}^{*}$ as follows.
At each step we take the midpoint $q^*$ of the current search list (initially $Q_{S}^{*}$), 
and compute the value of $\tau(q^*)$ in constant time.
We then take two points on each side of $q^*$ at epsilon distance on the boundary of $Q$.
Two possible cases arise:
If $q^*$ is a local maximum of $\tau$, then the algorithm returns $q'=q^*$; 
otherwise we determine if $q'$ lies to the left or to the right of $q^*$.
We eliminate half of the list according to the position of $q'$ and repeat recursively,
formally the algorithm is described as follows.
\begin{algorithm}\label{alg:SearchInQ}
\caption{Search for $q'$ on $Q_{S}^{*} = \{q_0, q_1, \ldots, q_{k}\}$}
\begin{algorithmic}[1]
	\STATE Define the initial search interval, $g\gets 0, h\gets k$
	\STATE Create a pointer to the middle element on the list, $i\gets \lceil \frac{g+h}{2}\rceil$
	\STATE Define $q_i^+\gets q_i + \varepsilon(q_{i+1} - q_i)$ and $q_i^-\gets q_i + \varepsilon(q_{i-1} - q_i)$
	\STATE Compute the radius of $C(p_0q_ip_1), C(p_0q_i^+p_1)$ and $C(p_0q_i^-p_1)$
	\IF{$\tau(q_i) > \max\{\tau(q_i^+),\tau(q_i^-)\}$}
		\STATE Finish and return $q' = q_i$
	\ELSE
		\IF{$\tau(q_i) < \tau(q_i^+)$}
			\STATE Redefine the search interval, $g\gets i$
		\ENDIF 
		\IF{$\tau(q_i) < \tau(q_i^-)$}
			\STATE Redefine the search interval, $h\gets i$
		\ENDIF
	\ENDIF
	\IF{$h = g+1$}
		\STATE Finish and return the segment $H=[q_g,q_{g+1}]$
	\ELSE
		\STATE Return to step 2
	\ENDIF
\end{algorithmic}
\end{algorithm}


This algorithm returns either the value of $q'$ if it is a vertex of $Q$, or a segment $H = (q_i,q_{i+1})$ of $Q_S$ such that $q'$ belongs to $H$. 
In the first case we are done since $c'$ is the center of  $C(p_0q'p_1)$, thus it can be determined in constant time given the position of $q'$. 
In the second case, the problem is reduced to that of finding a point $c'$ in the segment $S$ 
such that $d(c', p_0) = d(c',H)$. Therefore since $S$ and $H$ are line segments, this case can be solved with a quadratic equation in constant time.

Note that each step of the binary search requires constant time, thus
the algorithm finds the point $q'$ in $O(\log m)$ time once $S$ has been determined, the next result follows.

\begin{theorem}
After preprocessing a convex polygon $P$ on $n$ vertices in linear time into a data structure of size $O(n)$,
the minimum separating circle between $P$ and a query convex polygon $Q$ can be found in $O(\log n \log m)$ time.
\end{theorem}

\section{Closing Remarks}
In this paper we addressed, as far as we know, the first dynamic algorithm to find the minimum separating circle between polygons.
We achieve a polylogarithmic query running time by preprocessing $P$ into a data structure, 
so that given any query convex polygon $Q$, 
we can compute the minimum separating circle efficiently using the convexity of $Q$.
Nevertheless the next question is still open:\linebreak
Is it possible to find the minimum separating circle in less that $O(\log n \log m)$ time using $O(n)$ preprocessing time and space?


\begin{thebibliography}{4}

\bibitem{DigitalDiskAndCompacness}
C. E. Kim and T. A. Anderson, Digital disks and a digital compactness measure,
\emph{STOC '84: Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing}, (1984), 117--124.

\bibitem{ComputingCircularSeparabilityOfPlanarPointSets}
B. K. Bhattacharya, Circular separability of planar point sets, 
\emph{Computational Morphology} (1988), 25--39.


\bibitem{SeparatingPointsByCricles}
S. Fisk, Separating points by circles and the recognition of digital discs, 
\emph{IEEE Trans. Pattern Anal. Mach. Intell.} (1986), 8(4):554--556.

\bibitem{ComputingExtremeDistancesBetweenConvexPolygons}
H. Edelsbrunner, Computing the extreme distances between two convex polygons, 
\emph{Journal of Algorithms} \textbf{6} (1985), 213--224.		

\bibitem{MinimumPolygonalSeparation}
H. Edelsbrunner and F. P. Preparata, Minimum polygonal separation, 
\emph{Inform. Comput.} (1988), 77:218--232.

\bibitem{ComputingCircularSeparability}
J. O'Rourke, S. R. Kosaraju and N. Megiddo, Computing circular separability, 
\emph{Discrete and Computational Geometry} \textbf{1} (1986), 105--113.

\bibitem{SeparationBySphericalSurfaces}
S.R. Lay, On separation by spherical surfaces, 
\emph{Amer. Math. Monthly} \textbf{1} (1971), 78:1112--1113.


\bibitem{LinearTimeAlgorithmsForLinearProgramming}
N. Megiddo, Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems, 
\emph{SIAM Journal on Computing} \textbf{12} (1983), 759--776.

\bibitem{LinearProgrammingInLinearTime}
N. Megiddo, Linear programming in linear time when the dimension is fixed, 
\emph{J. ACM} \textbf{31} (1984), 114--127.


\bibitem{LinearVoronoiDiagramForConvexPolygon}
A. Aggarwal, L. J. Guibas, J. Saxe and P. W. Shor, A linear-time algorithm for computing the Voronoi diagram of a convex polygon,
\emph{Discrete Comput. Geom.} \textbf{4} (1989), 591--604.


\bibitem{ConstrainedMinimumEnclosingCircleWithCenterOnAQueryLineSegment}
S. Roy, A. Karmakar, S. Das and S. C. Nandy, Constrained minimum enclosing circle with center on a query line segment,
\emph{Computational Geometry} \textbf{42} (2009), 632--638.

\bibitem{DasJoseph:1990}
G. Das and D. Joseph, The complexity of minimum convex nested polyhedra,
\emph{In Proc. 2nd Canad. Conf. Comput. Geom.} (1990), 296--301.

\bibitem{Aggarwal:1985}
A. Aggarwal,  H. Booth, J. O'Rourke, S. Suri and C.K. Yap, Finding minimal convex nested polygons,
\emph{Proceedings of the first annual symposium on Computational geometry} (1985), 296--304.


\end{thebibliography}

\end{document}
